package cn.edu.xjtu.work.deleteDuplicates;

import cn.edu.xjtu.Util.ListNode.ListNode;
import cn.edu.xjtu.Util.ListNode.ListNodeUtil;
import cn.edu.xjtu.Util.TreeNode.TreeNode;

/**
 * 83. 删除排序链表中的重复元素
 * 
 * 存在一个按升序排列的链表，给你这个链表的头节点head，请你删除所有重复的元素，使每个元素只出现一次 。 返回同样按升序排列的结果链表。
 */
public class Solution {
  public static void main(String[] args) {
    ListNode head = new ListNode(1);
    ListNode temp = head;
    temp.next = new ListNode(1);
    temp = temp.next;
    temp.next = new ListNode(1);
    temp = temp.next;
    // temp.next = new ListNode(3);
    // temp = temp.next;
    // temp.next = new ListNode(4);
    // temp = temp.next;
    // temp.next = new ListNode(5);
    // temp = temp.next;
    // temp.next = new ListNode(5);
    // temp = temp.next;
    ListNodeUtil.print(deleteDuplicates1(head));
  }

  /**
   * 逐个检查当前元素与下一个元素是否相同
   * 
   * @param head
   * @return
   */
  public static ListNode deleteDuplicates(ListNode head) {
    if (head == null) {
      return null;
    }
    ListNode cur = head.next;
    int val = head.val;
    ListNode pre = head;
    while (cur != null) {
      if (cur.val == val) {
        pre.next = cur.next;
        cur = pre.next;
      } else {
        val = cur.val;
        cur = cur.next;
        pre = pre.next;
      }
    }
    return head;
  }

  /**
   * 不需要保存前驱节点
   * 
   * @param head
   * @return
   */
  public static ListNode deleteDuplicates1(ListNode head) {
    if (head == null) {
      return head;
    }

    ListNode cur = head;
    while (cur.next != null) {
      if (cur.val == cur.next.val) {
        cur.next = cur.next.next;
      } else {
        cur = cur.next;
      }
    }

    return head;
  }

}
